1. Field of Invention
This invention relates to collision avoidance in a communication layer two protocol, and more specifically, to a collision avoidance mechanism suitable to networking, low processing power devices, connected through an Ethernet hub.
2. Discussion of Prior Art
In modern systems it is very common to find a set of individual devices, each one with its own functions, capable of sharing information with each other through some kind of communication media. A clear example of such systems comes from a computer network. A local computer network is defined as a group of personal computers geographically located in a house or building. It is called Local Area Network (LAN) and comprises a group of personal computers sharing information, such as files, services, etc. The most cost-effective solution to such shared network is the utilization of only one physical media for all nodes present on the network. In this scheme, every device has the same right to use the unique channel to communicate with other device(s). A mechanism included in every device must be responsible for sharing the communication channel in an efficient manner.
The most popular type of computer network uses the Carrier Sense Multiple Access with Collision Detection (CSMA/CD) algorithm. A group of standards called 802, published by the IEEE, use this algorithm on different types of physical media.
The CSMA/CD algorithm senses first the communication media to determine if any other device is using it to transmit its information. If the channel is free, transmission starts but the channel is still sensed. If corrupt data is detected (sent information is different from actual channel content), transmission is aborted and each device involved in such collision backs off for a random time before sending the information again. Even when useful channel time is wasted on a collision, this mechanism has proved to satisfy the needs of a network that must be scalable to a great number of devices, in the order of hundreds of personal computers.
One of the most used CSMA/CD network is the 10BaseT Ethernet standard, which is very similar to the IEEE 802.3 standard. The Ethernet standard defines the type of physical media along with its electrical and timing characteristics. It works at 10 Mbps with Manchester bit encoding. It also defines the Media Access Control (MAC) with the CSMA/CD algorithm. When a device wants to transmit information to another device, the MAC layer of each device handles the recognition of the destination address in order to accept or refuse such packet. Such address is called MAC address, because it identifies the device accessing the communication channel. The MAC address is a 6-bytes unique identification number present on each device compatible with the Ethernet standard.
All devices connected to a 10BaseT Ethernet network use a twisted pair cable called UTP (Unshielded Twisted Pair) cable. A segment of UTP cable comes from each personal computer and is attached to a central device, which is responsible to connect all computers with each other. Initially, such device was called Ethernet hub. As said earlier, the hub takes any information coming from one of its connections and sends it to all other computers attached to it. It works as a repeater. Another device, called Ethernet switch, takes a step further and each connected computer is treated as an independent port, so information sent from one port to another doesn't have to be repeated to every other computer. It is directly sent from origin to destination port. Switches increase the performance, allowing a greater number of connected devices, but the cost is higher compared to a hub.
Due to its extended use, Ethernet LANs have not been limited to personal computers. Several devices used in industrial control and automation use this standard as the basis of communication network. It is also used in building and home automation, facilitating the merging of data computer networks and control networks. Having control devices attached to Ethernet networks makes it possible to perform remote configuration from a personal computer, reducing operational costs. It also allows the use of the personal computer as the monitoring station for the automation control network.
In order to make such control device interoperable with a personal computer, the communication protocol used by the computer must be present into the control device also. The most common protocol used by personal computers is the TCP/IP (Transfer Control Protocol/Internet Protocol). The IP protocol works at a lower level and is responsible for defining the logic address of each computer. That address is called the IP address, and each computer present on the same LAN must have different IP addresses. TCP protocol handles the integrity of the information and establishment of connections to transfer information between two devices present on the network in a reliable context. It is capable of fragmenting the information to make it more suitable for transmission over Ethernet networks. It also handles reordering of all pieces of incoming data and guarantees the correct arrival of all sent information. The TCP protocol is connection-oriented. A connection-oriented protocol has to ask for a connection to be opened. After the destination device accepts the connection petition, data transfer takes place, and finally the connection is closed by either of the two devices.
Another common protocol is the UDP/IP (User Datagram Protocol/Internet Protocol). Contrary to TCP, UDP protocol doesn't provide any reliability and it doesn't use any connection mechanism. It is called a message-oriented protocol, since each data packet goes from source to destination without any open-accept-transfer-close process.
As was stated before, the merging of a data network with a control network can be made only if both the personal computer and the control device handle the same communication protocol. In home automation specifically, low cost is one of the primary requirements for control devices. Such devices must be simple enough to keep cost down. That simplicity is achieved by using low processing power microcomputers, or most often, low processing power microcontrollers. This invention considers a low processing power microcontroller working at 8-bits, with 512 bytes (or less) of RAM registers and 8 k bytes (or less) of effective program memory. From this point and on the term microcontroller alone will be used as a reference to low processing power microcontrollers.
The TCP protocol is a very memory-demanding protocol, making difficult its implementation in a microcontroller. The UDP protocol instead requires much less memory resources, so its implementation in a microcontroller is easier.
Since home automation devices share the same Ethernet network with personal computers, they should behave as another connected computer in order to be recognized by them. The Dynamic Host Configuration Protocol (DHCP), defined on the public document RFC2131 and published by the Network Working Group, was created for a personal computer attached to a network to obtain automatically its IP address. Even when this protocol works with the UDP protocol, it requires sending and receiving UDP packets more than 100 bytes long. Some microcontrollers don't contain enough RAM registers to cover this requirement.
With such limitations, control devices can't be considered as personal computers also, even when they are attached to the same LAN.
Thus, there is the need for a specialized and simple mechanism with low memory and protocol requirements (UDP protocol, with data packets from 16 up to 64 bytes long), capable of handling network management functions, as IP address assignment, presence detection or any other function involving all connected control devices.
In accordance to these characteristics, a control network manager installed on a computer could use UDP broadcasting messaging to communicate with every control device. If a given broadcast message generates a response from each control device, a problem arises since all of them would try to respond at the same time. As was stated before, the Ethernet standard considers a back-off algorithm to handle network collisions, but in case of having 32 (which could be real numbers for a home automation systems) control devices, collisions would still occur on every retry, and the back-off algorithm would fail.
This multiple collision condition only occurs when Ethernet hubs are used, because they work as repeaters. Ethernet switches can handle such situation avoiding multiple collisions.
However, home automation is very likely to see hubs instead of switches, since their cost is considerably lower and the number of devices attached would rarely be more than 32 or 64. This invention to provides a simple mechanism to avoid multiple collisions occurring in an Ethernet network using hubs, in accordance to home automation control devices with limited processing power.